package 中等.搜索.回溯;

import java.math.BigDecimal;

/**
 * 给你一个仅由数字组成的字符串 s 。
 * 请你判断能否将 s 拆分成两个或者多个 非空子字符串 ，使子字符串的
 * 数值 按 降序 排列，且每两个 相邻子字符串 的数值之 差 等于 1 。
 * 例如，字符串 s = "0090089" 可以拆分成 ["0090", "089"] ，数值为
 * [90,89] 。这些数值满足按降序排列，且相邻值相差 1 ，这种拆分方法可行。
 * 另一个例子中，字符串 s = "001" 可以拆分成 ["0", "01"]、["00", "1"]
 * 或 ["0", "0", "1"] 。然而，所有这些拆分方法都不可行，因为对应数值分
 * 别是 [0,1]、[0,1] 和 [0,0,1] ，都不满足按降序排列的要求。
 * 如果可以按要求拆分 s ，返回 true ；否则，返回 false 。
 * 子字符串 是字符串中的一个连续字符序列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/splitting-a-string-into-descending-consecutive-values
 */
public class 将字符串拆分为递减的连续值_1849 {

    public static void main(String[] args) {

        将字符串拆分为递减的连续值_1849 impl = new 将字符串拆分为递减的连续值_1849();
        System.out.println(impl.splitString("1234"));

    }

    /**
     * 回溯+剪枝
     */
    public boolean splitString(String s) {

        for (int i = 1; i < s.length(); i++) {
            if (dfs(new BigDecimal(s.substring(0, i)), i, s)) {
                return true;
            }
        }

        return false;
    }

    // 判断从 left 索引开始往后截取，截取的值 = pre -1
    public boolean dfs(BigDecimal pre, int left, String s) {
        if (left == s.length()) {
            return true;
        }

        for (int right = left + 1; right <= s.length(); right++) {
            BigDecimal cur = new BigDecimal(s.substring(left, right));

            // 剪枝，如果当前值大于前面的值，往后遍历越大，直接返回false
            if (cur.compareTo(pre) > 0) {
                return false;
            }

            if (pre.subtract(cur).compareTo(new BigDecimal(1)) == 0 && dfs(cur, right, s)) {
                return true;
            }
        }

        return false;
    }

}
